// 超级慢
function split(nums) {
    let zeroCount = 0;
    const nonezero = [];
    nums.forEach((n) => {
      if (n === 0) zeroCount++;
      else nonezero.push(n);
    });
    return {
      zeroCount,
      nonezero: nonezero.sort()
    };
  }
  
  function sum33(nums) {
    if (nums.length < 3) return [];
  
    let map = new Map();
    nums.forEach((n) => {
      let c = map.get(n);
      if (c === null || c === undefined) {
        map.set(n, 1);
      } else {
        map.set(n, c + 1);
      }
    });
  
    const ds = new Set();
  
    const result = [];
  
    for (let i = 0; i < nums.length; i++) {
      const first = nums[i];
      for (let j = 0; j < nums.length; j++) {
        if (i === j) continue;
        const second = nums[j];
        const target = 0 - first - second;
        const targetCount = 1 + (target === second ? 1 : 0) + (target === first ? 1 : 0);
        if (map.get(target) >= targetCount) {
          // bingo
          const solu = [ first, second, target ].sort();
          const dk = `${solu[0]},${solu[1]},${solu[2]}`;
          if (!ds.has(dk)) {
            result.push(solu);
            ds.add(dk);
          }
        }
      }
    }
  
    return result;
  }
  
  function sum32(nums) {
    if (nums.length < 2) return [];
    let map = new Map();
    nums.forEach((n) => {
      let c = map.get(n);
      if (c === null || c === undefined) {
        map.set(n, 1);
      } else {
        map.set(n, c + 1);
      }
    });
  
    const ds = new Set();
  
    const result = [];
  
    for (let i = 0; i < nums.length; i++) {
      const first = nums[i];
      const target = 0 - first;
      const targetCount = 1 + (target === first ? 1 : 0);
      if (map.get(target) >= targetCount) {
        // bingo
        const solu = [ first, 0, target ].sort();
        const dk = `${solu[0]},${solu[1]},${solu[2]}`;
        if (!ds.has(dk)) {
          result.push(solu);
          ds.add(dk);
        }
      }
    }
    return result;
  }
  
  
  /**
   * @param {number[]} nums
   * @return {number[][]}
   */
  var threeSum = function(nums) {
    if (nums.length < 3) return [];
  
    const { zeroCount, nonezero } = split(nums);
    switch (zeroCount) {
      case 0:
        return sum33(nonezero);
      case 1:
      case 2:
        return [ ...sum33(nonezero), ...sum32(nonezero)];
      default:
        return [ ...sum33(nonezero), ...sum32(nonezero), [ 0, 0, 0 ] ];
    }
  };